package sort;

import java.lang.reflect.Array;
import java.util.Arrays;

public class sort1 {

    //冒泡排序
    public int[] sortArray(int[] nums) {
            int len=nums.length;
            if (len==0||len==1) return nums;
            for (int i=1;i<=len;i++){
                for (int j=0;j<len-1;j++){
                    if (nums[j]>nums[j+1]){
                        int temp=nums[j];
                        nums[j]=nums[j+1];
                        nums[j+1]=temp;
                    }
                }
            }
            return nums;
    }

   //选择排序
   public int[] sortArray2(int[] nums) {
       int len=nums.length;
       if (len==0||len==1) return nums;
       for (int i=0;i<nums.length;i++){
           int minindex=i;
           for (int j=i+1;j<nums.length;j++){
               if (nums[j]<nums[minindex]){
                   minindex=j;
               }
           }
           if (minindex!=i){
               int temp=nums[minindex];
               nums[minindex]=nums[i];
               nums[i]=temp;
           }
       }
       return nums;
   }

   //归并排序
   public int[] sortArray3(int[] nums) {
        if(nums.length<2) return nums;
        int mid=nums.length/2;
       int[] ints = Arrays.copyOfRange(nums, 0, mid);
       int[] ints1 = Arrays.copyOfRange(nums, mid, nums.length);
       //这个传入合并函数的，应该是排序后的两个数组，不是直接传入ints/ints1
       return merge(sortArray3(ints),sortArray3(ints1));
   }
   public int[] merge(int[] a1,int[] a2){
        int len1=a1.length;
        int len2=a2.length;
        int[] res=new int[len1+len2];
        int p1=0;
        int p2=0;
        int i=0;
        while (p1<len1&&p2<len2){
            if (a1[p1]<=a2[p2]){
                res[i]=a1[p1];
                p1++;
                i++;
            }else {
                res[i]=a2[p2];
                p2++;
                i++;
            }
        }
        while (p1<len1){
            res[i]=a1[p1];
            p1++;
            i++;
        }
       while (p2<len2){
           res[i]=a2[p2];
           p2++;
           i++;
       }
       return res;
   }

   //插入排序
   public int[] sortArray4(int[] nums) {
            if (nums.length<2) return nums;
            //记录待插入的元素的下标
            int index=1;
            while (index<nums.length){
                int temp=nums[index];
                int j=index-1;
                while (j>=0){
                    if (nums[j]>=temp){
                        nums[j+1]=nums[j];
                        //一个一个往后串
                        j--;
                    }else {
                        //此时找到了要插入的位置，就是当前位置的后一个位置，直接插入即可
                        nums[j+1]=temp;
                        break;
                    }
                }
                //判断是否是因为遍历到头了还没有找到插入位置，如果是的话，就把它插入到头位置
                if (j==-1) nums[0]=temp;
                index++;
            }
            return nums;
   }

   //快速排序
   public int[] sortArray5(int[] nums) {
        if (nums.length<2) return nums;
        return quickSort(nums,0,nums.length-1);
   }
   public int[] quickSort(int[] nums,int start,int end){
        if (nums.length<0||start>end||end>nums.length-1||start<0) return null;
        int index=partition(nums,start,end);
        if (start<index)
            quickSort(nums,start,index-1);
        if (index<end)
            quickSort(nums,index+1,end);
        return nums;
   }

   public int partition(int[] arr,int start,int end){
        if (start==end) return start;
        //这里一定要随机产生划分值，随机产生比固定值快很多！！
        int randomIndex=(int)(start+(end-start)*Math.random());
        //将选择出来的划分值放到最后一位
        int temp=arr[randomIndex];
        arr[randomIndex]=arr[end];
        arr[end]=temp;
        //划分点
        int res=start-1;
        for (int i=start;i<=end;i++){
            if (arr[i]<=arr[end]){
                res++;
                if (res<arr[i]){
                    int temp2=arr[res];
                    arr[res]=arr[i];
                    arr[i]=temp2;
                }
            }
        }
        return res;
   }

   //希尔排序
   public int[] sortArray6(int[] nums) {
        if(nums.length<2) return nums;
        int temp;
        int gap=nums.length/2;
        while (gap>0){
            for (int i=gap;i<nums.length;i++){
                temp=nums[i];
                int preIndex=i-gap;
                while (preIndex>=0&&nums[preIndex]>temp){
                    nums[preIndex+gap]=nums[preIndex];
                    preIndex-=gap;
                }
                nums[preIndex+gap]=temp;
            }
            gap/=2;
        }
        return nums;
   }

   //计数排序
   public int[] sortArray7(int[] nums) {
            if (nums.length<2) return nums;
            int min=nums[0];
            int max=nums[0];
            for (int i=0;i<nums.length;i++){
                if (nums[i]<min)
                        min=nums[i];
                if (nums[i]>max)
                        max=nums[i];
            }
            //原数组对应计数数组的偏移量
            int bias=min;

            int[] countArray=new int[max-min+1];

            //得到了计数数组
            for (int i=0;i<nums.length;i++){
                countArray[nums[i]-min]++;
            }
            int orinigali=0; //原始数组指针
            int counti=0;   //计数数组指针
            while (orinigali<nums.length){
                while (countArray[counti]!=0){
                    nums[orinigali]=counti+bias;
                    countArray[counti]--;
                    orinigali++;
                }
                counti++;
            }
            return nums;

   }



    public static void main(String[] args) {
        int[] arr={5,2,3,1};
        new sort1().sortArray3(arr);
    }
}
